/**
 * 240. 搜索二维矩阵 II
 * https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
 */

// /**
//  * @param {number} target
//  * @param {number[][]} matrix
//  * @param {number} begin
//  * @param {number} end
//  * @param {number} line
//  * @param {boolean} vertical
//  * @return {number}
//  */
// function search(target, matrix, begin, end, line, vertical) {
//   let left = begin;
//   let right = end;
//   let middle;
//   while (left <= right) {
//     middle = Math.floor((left + right) / 2);
//     if (vertical) {
//       if (matrix[middle][line] === target) {
//         return middle;
//       }
//       if (matrix[middle][line] > target) {
//         right = middle - 1;
//       } else {
//         if (middle === end || matrix[middle + 1][line] > target) {
//           return middle;
//         }
//         left = middle + 1;
//       }
//     } else {
//       if (matrix[line][middle] === target) {
//         return middle;
//       }
//       if (matrix[line][middle] > target) {
//         right = middle - 1;
//       } else {
//         if (middle === end || matrix[line][middle + 1] > target) {
//           return middle;
//         }
//         left = middle + 1;
//       }
//     }
//   }
//   return -1;
// }
//
// /**
//  * @param {number[][]} matrix
//  * @param {number} target
//  * @return {boolean}
//  */
// function searchMatrix(matrix, target) {
//   let startX = 0;
//   let startY = 0;
//   let endX = matrix[0].length - 1;
//   let endY = matrix.length - 1;
//   while (startX <= endX && startY <= endY) {
//     const verticalIndex = search(target, matrix, startY, endY, startX, true);
//     if (verticalIndex < 0) {
//       return false;
//     }
//     if (matrix[verticalIndex][startX] === target) {
//       return true;
//     }
//     endY = verticalIndex;
//     startX += 1;
//     const horizontalIndex = search(target, matrix, startX, endX, startY, false);
//     if (horizontalIndex < 0) {
//       return false;
//     }
//     if (matrix[startY][horizontalIndex] === target) {
//       return true;
//     }
//     endX = horizontalIndex;
//     startY += 1;
//   }
//   return false;
// }

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
function searchMatrix(matrix, target) {
  let x = matrix[0].length - 1;
  let y = 0;
  while (x >= 0 && y < matrix.length) {
    if (matrix[y][x] === target) {
      return true;
    }
    if (matrix[y][x] > target) {
      x -= 1;
    } else {
      y += 1;
    }
  }
  return false;
}

const src = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30],
];
for (let i = 0; i < src.length; i += 1) {
  for (let j = 0; j < src[i].length; j += 1) {
    console.log(searchMatrix(src, src[i][j]) === true);
  }
}
console.log(searchMatrix(src, -1) === false);
console.log(searchMatrix(src, 20) === false);
console.log(searchMatrix(src, 31) === false);
console.log(searchMatrix([[1]], 31) === false);
console.log(searchMatrix([[1]], 1) === true);
